1. Field of the Invention
The present invention relates to motion vector detecting method and apparatus and, more particularly, to motion vector detecting method and apparatus for processing blocks having smaller residual difference at an early stage of search.
2. Description of the Related Art
Conventionally, as a highly efficient compression coding method of an animation, H.261 and H.263 of an ITU-T (International Telecommunication Union-Telecommunication Standardization Sector) recommendation or MPEG-1 and MPEG-2 of a MPEG (Moving Picture Expert Group) recommendation in ISO (International Organization for Standardization) etc. are known. They are the highly efficient compression coding technique of time-varying images formed of combinations of techniques such as DCT (Discrete Cosine Transformation), inter-frame prediction by motion compensation, quantization, and variable length coding.
FIG. 13 is one example of a predictive coding apparatus for coding images using inter-frame prediction by motion compensation. In FIG. 13, image data is supplied to an input unit 100. Also, image data (hereinafter called xe2x80x9creference imagexe2x80x9d) of a frame connected in time series to a current input image (hereinafter called xe2x80x9ccurrent imagexe2x80x9d) is stored in frame memory 102.
A motion vector detecting unit 101 obtains a motion vector indicating correspondence every minor area of both the images using the current image supplied from the input unit 100 and the reference image supplied from the frame memory 102. The obtained motion vector is supplied to a motion compensation unit 103. The motion compensation unit 103 performs motion compensation processing using the motion vector supplied from the motion vector detecting unit 101 and the reference image supplied from the frame memory 102, and obtains image data (hereinafter called xe2x80x9cpredictive imagexe2x80x9d) to which the motion compensation processing is performed.
A subtracter 104 obtains image data (hereinafter called xe2x80x9cpredictive difference imagexe2x80x9d) subtracting the predictive image from the current image using the current image supplied from the input unit 100 and the predictive image supplied from the motion compensation unit 103.
A DCT (Discrete Cosine Transformation) unit 105 performs DCT to the predictive difference image supplied from the subtracter 104 and obtains a coefficient of DCT.
A quantizing unit 106 performs quantization processing to the coefficient of DCT supplied from the DCT unit 105. Output of the quantizing unit 106 is outputted from an output unit 107. Also, the output of the quantizing unit 106 is supplied to an inverse quantizing unit 108.
The inverse quantizing unit 108 performs inverse quantization processing to the quantized coefficient of DCT supplied from the quantizing unit 106 and obtains a coefficient of DCT. An inverse DCT unit 109 performs inverse DCT processing to the coefficient of DCT supplied from the inverse quantizing unit 108 and obtains difference data from the reference image.
An adder 110 adds the difference data to the predictive image to restore the current image using the difference data supplied from the inverse DCT unit 109 and the predictive image supplied from the motion compensation unit 103.
The frame memory 102 stores the restored current image supplied from the adder 110.
A switching unit 111 switches whether inter-frame prediction is performed or not, and the inter-frame prediction is performed if the switching unit 111 is turned on and the inter-frame prediction is not performed if the switching unit 111 is turned off.
In the compression coding using the inter-frame prediction thus, the difference data between the current image and the predictive image obtained by performing the motion compensation processing is encoded on the basis of the motion vector detected by the motion vector detecting unit. Because of this, the higher the detecting accuracy of the motion vector detected by the motion vector detecting unit, the smaller the amount of information on the difference data, with the result that coding efficiency is improved.
FIG. 14 illustrates motion vector detection used in the compression coding using such an inter-frame prediction. In FIG. 14, numeral 120 designates a current image and numeral 121 designates a reference image. In the motion vector detection, an image is divided into minor areas (hereinafter called xe2x80x9cblockxe2x80x9d) and a motion vector is obtained every block. For this purpose, a block 124 best matching a block 122 of the current image is detected within a search range 123 set in the reference image 121 to the block 122 within the current image 120.
The difference in position within the image between the block 122 of the current image and the block 124 best matching the block 122 within the search range 123 of the reference image in this case is a motion vector 125. As an evaluation value of matching between blocks, a total of square or absolute value of the difference of each pixel value within the block is often used. The case of using the total of absolute value of the difference of each pixel value within the block as the evaluation value of matching will be described below, and the total of absolute value of the difference of each pixel value within this block is called xe2x80x9cresidual differencexe2x80x9d.
As a method of motion vector detection, a block matching method is known. In the block matching method, a position of blocks within the set search range is moved, and the residual difference between the blocks in each position within the search range and blocks of the current image is obtained, and the block position so as to minimize the residual difference is obtained.
In the block matching method, the problem is that the amount of operation is large. For example, if it is assumed that the size of a block is 16 pixelsxc3x9716 pixels and the size of a search range is 15 pixels in longitudinal and transverse directions, respectively, and the residual difference is obtained at each integer pixel position within the search range, in order to obtain a motion vector of one block, calculations of the absolute value of 256 (=16xc3x9716) pixels of the difference have to be performed 961 (31xc3x9731) times. Further, in order to carry out this processing with respect to each block in the current image, the whole amount of operation becomes larger.
Because of this, a method of reducing the amount of operation of the block matching method is required. As the method of reducing the amount of operation, a SSDA (Sequential Similarity Detection Algorithm) method is known. This method is disclosed in, for example, DANIELI. BARNEA, HARVEY F. SILVERMAN, xe2x80x9cA Class of Algorithms for Fast Digital Image Registrationxe2x80x9d, IEEE Transactions on Computer, Vol. C-21, No.2, pp179-186, February, 1972. This method is designed so that attention is given to the nature that the residual difference remarkably increases in blocks having a little similarity and during calculation of the residual difference, the residual difference obtained in partway is compared with a certain threshold value and if the residual difference exceeds the threshold value, the calculation of the residual difference concerning said block is aborted and thereby, the amount of operation is reduced.
In the case of using this method, it becomes a problem in setting the threshold value for determining abort of the calculation of the residual difference. If the threshold value is too large, the amount of operation becomes large since the case capable of aborting the calculation of the residual difference decreases. On the contrary, if the threshold value is too small, the global minimum value cannot be searched and thus the possibility of outputting an inadequate motion vector is increased.
As for a method of setting the threshold value, there is, for example, an automatic determination method of the threshold value disclosed in xe2x80x9cOverlay of Image by Sequential Testing Method of Residual Differencexe2x80x9d by Morio Onoue, Norihiko Maeda, and Masaru Saitou, Information Processing, Vol. 17, No.7, pp634-640, July, 1976. This method uses the minimum value of the past residual difference as the threshold value. According to this method, the residual difference is first calculated without setting the threshold value and the calculated residual difference is set to the first threshold value and subsequently, the calculated residual difference is set to the new threshold value whenever the calculations of the residual difference are performed until the end of the block without aborting on the way and thereby, the global minimum value can always be searched.
In the case of using this method, order of movement in calculating the residual difference by moving a block position within a search range is important. That is, if blocks having smaller residual difference at an early stage of search are processed and the residual difference may be set to the threshold value, the case capable of aborting the calculation of the residual difference increases by the SSDA method, with the result that the amount of operation may be reduced. For this purpose, for example, in Telenor Research, xe2x80x9cTMN(H.263) Encoder/Decoder, Version 2.0xe2x80x9d, June, 1997, attention is given to the nature that the probability of occurrence of a motion vector having a small size is high, and a spiral search for starting a search from a position of a motion vector (0,0) within a search range and sequentially performing the search outwardly is used.
FIG. 15 is a block diagram illustrating a configuration example of a motion vector detecting apparatus using the spiral search. This motion vector detecting apparatus is regarded as a conventional example below.
In FIG. 15, a current image is supplied to a current image input circuit 130. Also, a reference image is inputted to a reference image input circuit 131. A search range setting circuit 132 sets a search range for motion vector detection to the reference image inputted from the reference image input circuit 131. The search range is set to, for example, the range defined by standards such as H.263, MPEG-2. Also, in order to reduce the amount of operation necessary for the motion vector detection, the search range may be set to the range narrower than the range defined by the standards. A spiral scan circuit 133 scans the inside of the search range of the reference image set by the search range setting circuit 132 in spiral order.
FIG. 16 illustrates an example of scan order of the search range by the spiral scan circuit 133. FIG. 16 is an example when the search range is three pixels in longitudinal and transverse directions, respectively, and a search is performed at integer pixel positions. In FIG. 16, circles indicate the integer pixel positions and a double circle indicates a pixel position of a motion vector (0,0) within a search range 140 and numerals written in the circles indicate order for scanning the pixel positions.
A residual difference calculation and minimum determination circuit 134 calculates the residual difference using blocks in the input image inputted from the current image input circuit 130 and blocks in the reference image scanned by the spiral scan circuit 133. Next, the calculated residual difference is compared with the minimum residual difference, and the minimum residual difference is updated if the calculated residual difference is smaller than the minimum residual difference. In this residual difference calculation and minimum determination, for example, the above-mentioned SSDA method and threshold automatic determination method are used.
FIG. 17 is a flowchart illustrating operations of the residual difference calculation and minimum determination circuit 134 using the SSDA method and threshold automatic determination method. As an initial value of the minimum residual difference, for example, the residual difference where a motion vector is (0,0) is set, and as an initial value of a motion vector, for example, a motion vector (0,0) is set. In the residual difference calculation and minimum determination, the residual difference is first initialized (step S100). Next, the residual difference concerning a part of a block is calculated and the result is added to the residual difference (step S101). Here, a part of the block means pixels such as one pixel, one row of pixels, half of the block, and must be determined by taking account of balance between the amount of operation capable of reduction by the SSDA method and the amount of operation newly caused by using the SSDA method.
Then, the intermediate result of the residual difference calculation is compared with the minimum residual difference (step S102). Here, if the intermediate result of the residual difference calculation is larger than the minimum residual difference, the residual difference calculation is aborted for termination since there is no possibility that the residual difference becomes not larger than the minimum residual difference even if the residual difference calculation is executed until the end of the block. Subsequently, it is determined whether the residual difference calculation of the whole block is terminated or not (step S103), and if not, the steps S101 and S102 are repeated. If so, the residual difference is compared with the minimum residual difference (step S104), and if the residual difference is smaller than the minimum residual difference, the minimum residual difference is updated to the current residual difference of the block and the motion vector is updated to the motion vector of the current block (step S105).
When the residual difference calculation and minimum determination is performed over the whole blocks within the search range set by the search range setting circuit 132, the motion vector of the block in which the residual difference becomes minimum is obtained, so that this motion vector is outputted from a motion vector output circuit 135.
FIG. 18 illustrates search order in the case of searching motion vectors in scan line order of a screen when scanning the inside of the search range of the reference image. Meaning etc. of reference characters indicated in FIG. 18 is similar to that indicated in FIG. 16.
On the contrary, in FIG. 16, a search is first performed from positions near a position of a motion vector (0,0) within the search range 140 by using a spiral search. In general, the probability of occurrence of a motion vector having a smaller size is higher. Thus, by performing the spiral search, blocks having small residual difference at an early stage of the search are processed and the case capable of aborting the residual difference calculation by the SSDA method increases. As a result, the amount of operation can be reduced more.
However, in the case of using the above spiral search, the blocks having smaller residual difference at an early stage of the search cannot be processed depending on the nature of images, so that there has been a problem that the amount of operation cannot be reduced. For example, in pan manipulation etc. of a camera, the motion vectors with the size larger than several pixels of row or column direction in many part within a screen appear. In this case, many blocks having small residual difference are located toward the outside of the search range. Thus, in the spiral search for always starting a search from a position of a motion vector (0,0) and sequentially performing the search outwardly, the blocks having smaller residual difference at an early stage of the search cannot be processed, with the result that the amount of operation cannot effectively be reduced.
Object of the Invention
It is an object of the present invention to process blocks having smaller residual difference at an early stage of a search and increase the number of blocks capable of aborting calculation of the residual difference on the way and detect motion vectors in a small amount of operation without lowering detection accuracy.
Summary of the Invention
In the present invention, scan order within a search range set in a reference image is set by using information on the previous motion vectors. That is, in the present invention, by performing scanning in order adapted for the nature of images, the number of blocks capable of aborting calculation of the residual difference on the way is increased at an early stage of a search. Concretely, for example, a motion vector of a block residing in the same position as the previous frame is set as a predictive vector of the motion vector of a block of an object of processing. Then, the end position of the predictive vector is set to the scan start position and scanning is spirally performed from the scan start position toward the vicinity of the outside of the search range. As a result, in the present invention, the motion vector can be detected in a small amount of operation without lowering detection accuracy.
Also, in the present invention, a search order setting circuit sets search order using information on the motion vectors stored in a motion vector storage circuit.
Further, in the present invention, space correlation rather than time correlation in time-varying images is used for obtaining the predictive vector of the motion vector of a block of an object of processing. For example, the predictive vector of the block of an object of processing is obtained from the motion vector of the block near the same frame, and scanning is spirally performed using the end point of the predictive vector as the scan start position.
Furthermore, in the present invention, when the scan order within the search range set by a search range setting circuit is set by using the information on the motion vectors stored in the motion vector storage circuit, the search order setting circuit provides plural scan orders previously and selects one of the provided plural scan orders on the basis of the information on the motion vectors stored in the motion vector storage circuit.